#include "stack_queue.h"
#include <iostream>
#include <string>
using namespace std;

void MyStack::printStack(){
    listNode* p = topNode;
     
    
    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

listNode::listNode()
{
    next = nullptr;
    data = 0;
}

listNode::listNode(int nodeData, listNode* succ){
    data = nodeData;
    next = succ;

}

MyStack::MyStack(){
    topNode = nullptr;
    stackSize = 0;
}

MyStack::~MyStack(){
    while(topNode != nullptr){
        listNode* p;
        p = topNode;
        topNode = p ->next;
        delete p;
    }//一个一个删

    stackSize = 0;
}

bool MyStack::push(const int& i){
    
    listNode * newn = new listNode(i , topNode);
    if(newn == nullptr){return false;}//地址分配失败

    topNode = newn;


    stackSize ++;
    return true;
}

bool MyStack::pop(int& i){

    if(topNode == nullptr){return false;}//空栈
    i = topNode ->data;

    listNode *p = topNode;
    topNode = topNode ->next;
    delete p;
    stackSize--;
    return true;
}

bool MyStack::getTop(int& i){
    if(topNode == nullptr){return false;}//空栈

    i = topNode ->data;
    return true;
}

bool MyStack::isEmpty(){
    return (topNode == nullptr);
}

MyQueue::MyQueue(const int& i){
    capacity = i;
    queue = new int[capacity];
    rear = 0;
    front = 0;
}

MyQueue::~MyQueue(){
    delete[] queue;

    queue = nullptr;
}

bool MyQueue::isFull(){
    return (rear +1) % capacity == front;//rear+1 = front就满了
    
}

bool MyQueue::enQueue(const int& i){//尾巴入
    if(isFull()){return false;}
    queue[rear] = i;
    rear++;//保持rear为空
    return true;
}

bool MyQueue::deQueue(int& i){//头出
    if(rear == front){return false;}//没东西
    i = queue[front];
    front++;//逻辑上删除而物理上不删除
    return true;
}

bool MyQueue::getFront(int& i){//不删除
    if(rear == front){return false;}//empty
    i = queue[front];
    return true;

}

bool MyQueue::isEmpty()
{
    return front == rear; 
}
int cmp( int isp , int icp){
    if(isp > icp){//栈顶op优先级高于当前op
        return 1;
    }
    if(isp < icp){//栈顶op优先级低于当前op
        return 2;
    }
    if(isp == icp && icp == 0){//测到#
        return 3;
    }
    if(isp == icp && icp == 1){//（与）相遇
        return 4;    
    }

    return 0;
}

bool postfixExpression(const string& tar, string& j){
    MyStack A;
    char a;//存符号，数字
    int icp, isp;//栈外栈内优先级
    int op;//用来接收字符
    int ind;//用来接收索引


    string i = tar;
    i.push_back('#');//以#结尾

    A.push(-1);//第-1个位置,无意义，一个存位置，下面存isp
    A.push(0);//压住底,0 = #

    int k = 0;
    for(k;k < i.size(); k++)
    {

        a = i[k];//一个一个扫描，此时为栈外优先级icp

        switch (a)//用列表
        {
        case '#': 
            icp = 0;//扫完了
            break;

        case '(': 
            icp = 8;
            break;//8最大了，自动起隔断作用
        
        /*case '^': 
            icp = 6;
            break;似乎不用实现 ^ %*/

        case '*':
        case '/':
            icp = 4;
            break;

        case '+':
        case '-':

            icp = 2;
            break;

        case ')': 
            icp = 1;
            break;
        
        default:
            j.push_back(a);//数字放进去
            continue;
        }

        A.getTop(isp);//栈内

    

        do{
        switch (cmp(isp , icp))
        {
        case 1://栈顶op优先级高于当前op isp > icp
            
            A.pop(op);
            A.pop(ind);//接收索引

            if(isp == 1){
                j.clear();
                return false;}//呃，未匹配的（
            

            j.push_back(i[ind]);//把op发到后缀式子
            A.getTop(isp);//更新栈内级

            if(icp == 1 && isp == 0){
                j.clear();
                return false;}//）没找到（

            break;
        
        case 2://栈顶op优先级低于当前op  isp < icp

            
            A.push(k);//存索引
            
            if(icp == 8){A.push(1);}//存（
            else {A.push(icp+1);}//存其他的

            A.getTop(isp);//更新栈内级
            icp = 9;//当前op已经压入栈，不能再参与cmp了
            
            break;

        case 3://测到#
            A.pop(op);
            A.pop(ind);
                       
            if(A.isEmpty()){return true;}
            
            j.clear();
            return false;//没空，杀！

        case 4://此时（遇到了）
           
            A.pop(op);
            A.pop(op);//取出（和索引

            
            A.getTop(isp);//更新栈内级
            
            icp = 9;//当前op是），与（完成配对，不能再参与cmp了
            break;

        case 0:
            j.clear();
            return false;//有错

        }
        }while(cmp(isp , icp) == 1 || 
               cmp(isp , icp) == 4 ||
               cmp(isp , icp) == 3);//处理多次出栈和括号匹配,##匹配
    }

    j.clear();
    return false;
}

bool expressionVal(const string& i, int& j){
    MyStack A;//存放数字，op
    char a;//扫描用
    int c,d,e;//计算用

    string tar;

    if(postfixExpression( i, tar )){}
    else{return false;}//表达式错误

    int k = 0;
    for(k; k < tar.size(); k++){
        a = tar[k];
        if('0' <= a && '9' >= a){//扫到数字了
            int b = a - '0';
            A.push(b);
        }
        else if(a == '+' ||
           a == '-' ||
           a == '*' ||
           a == '/' )
        {//直接列出来
            
            if(A.pop(d) && A.pop(c))
            {//检测是否有两个数
                switch (a)
                {
                case '+':
                    e = c + d;//+
                    break;
                case '-':
                    e = c - d;//-
                    
                    break;
                case '*':
                    e = c * d;//*
                    break;
                case '/':
                    if(d == 0){return false;}//除数！=0

                    e = c / d;// /
                    break;
                }
            }
            A.push(e);
        
        }
        else
        {
            return false;//扫到未知数了
        }

        
    }

    A.pop(e);


    if(A.pop(e)){
        return false;
    }//栈里有东西

    j = e;

    return true;

}




void yanghui(const int& n) {
  if (n <= 0) return;
  

   
    MyQueue q(n + 4); //容量设为n+4，确保足够存

    
    q.enQueue(1);//第一行
    q.enQueue(1);

    q.printQueue();

    
    for (int i = 1; i <= n; ++i) {
        int prev = 0; //用于计算当前元素的前一个元素
        int cur;

       
        q.enQueue(0); //先入一个0作为下一行计算的辅助

        
        MyQueue p(n + 4); //输出行

        // 利用上一行元素计算当前行
        while (!q.isEmpty()) {
            q.deQueue(cur);
            p.enQueue(prev + cur); // 前一个元素与当前元素相加
            prev = cur; // 更新前一个元素
        }

        p.printQueue();

        
        while (!p.isEmpty()) {//更新队列，存下一行
            p.deQueue(cur);
            q.enQueue(cur);
        }
    }

}